import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import javax.swing.tree.TreeNode;

/*
 * @lc app=leetcode.cn id=94 lang=java
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // //递归写法
    // public List<Integer> inorderTraversal(TreeNode root) {
    //     List<Integer> res=new ArrayList();
    //     inorder(root,res);
    //     return res;
    // }

    // public void inorder(TreeNode node,List<Integer> res){
    //     if(node==null){
    //         return;
    //     }
    //     inorder(node.left, res);
    //     res.add(node.val);
    //     inorder(node.right, res);
    // }
    public List<Integer> inorderTraversal(TreeNode root) {
        //非递归写法
        List<Integer> res=new ArrayList<>();
        if(root!=null){
            Deque<TreeNode> stack=new ArrayDeque<>();
            TreeNode cur=root;
            while(cur!=null||!stack.isEmpty()){
                if(cur!=null){
                    stack.push(cur);
                    cur=cur.left;//左
                }else{
                    cur=stack.pop();
                    res.add(cur.val);
                    cur=cur.right;//右
                }
            }
        }
        return res;
    }

}
// 非递归第二种写法，更好理解，将二叉树分为左边和右边即可
// class Solution {
//     public List<Integer> inorderTraversal(TreeNode root) {
//         List<Integer> res=new ArrayList<>();
//         if(root==null) return res;
//         Deque<TreeNode> stack=new ArrayDeque<>();
//         TreeNode cur=root;
//         while(cur!=null||!stack.isEmpty()){
//             while(cur!=null){
//                 stack.push(cur);
//                 cur=cur.left;
//             }//左边一直入栈
//             cur=stack.pop();//然后处理节点即可（左中其实就一起处理了）
//             res.add(cur.val);
//             cur=cur.right;//右
//         }
//         return res;
//     }
// }
// @lc code=end

